// https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
// https://www.bilibili.com/video/BV137411B7BN?from=search&seid=2795649807609132809
// https://www.bilibili.com/video/BV1rT4y1u7jV?from=search&seid=4351844903764192177

class Solution
{
public:
  int lengthOfLIS(vector<int> &nums)
  {
    int n = (int)nums.size();

    if (n == 0)
      return 0;

    // 1. 定义状态转移数组
    // dp[i]=n 表示以【节点i】作为【结束节点】时，最大上升子序列中【元素总个数】
    vector<int> dp(n, 0);

    // 2. 计算得到以每一个元素为【结束】时，最大升序子序列的总个数
    for (int i = 0; i < n; ++i) // 1层循环 i [0, n-1]
    {
      // dp[i] 默认值 1（每一个元素自己，就是一个上升子序列）
      dp[i] = 1;

      // 遍历【i之前】的每一个元素
      for (int j = 0; j < i; ++j) // 2层循环 j [0, i-1]
      {
        if (nums[j] >= nums[i]) // 控制【升序】
          continue;

        // 当前节点的最大上升子序列总个数 dp[i] = dp[i] 和 dp[j]+1 的最大值
        dp[i] = max(
          dp[i], // 当前节点 i 结束时，最大上升子序列的个数
          dp[j] + 1 // i 之前的节点 j(0,i-1) 结束时，最大上升子序列的个数 + 1
        );
      }
    }

    // 3. 返回【最大的】dp[i] 值
    return *max_element(dp.begin(), dp.end());
  }
};